The invention relates to programmable state machines and more particularly to programmable packet classification state machines for use in high-speed communication.
In the past, programmable state machines were provided with procedural programming. This permits flow from one state to another state upon certain conditions according to a desired sequence. Because a state machine effectively controls a sequence of processing steps, the concept of a truly non-procedural programming method for a state machine appears contradictory. To this end, many xe2x80x9cnon-proceduralxe2x80x9d methods of programming state machines have been proposed. Nevertheless, upon analysis these have been found to be procedural or somewhat procedural. The concept of branches and loops is common in these methods and a flow diagram of operation is often evident.
Until now because of the procedural nature of state machines, non-procedural methods of programming the state machines have been regarded as having few advantages. Some of the xe2x80x9cnon-proceduralxe2x80x9d methods of programming a state machine focus on reuse of programming code and modularity of the code. Therefore, procedural elements within each state are not only permitted, but are viewed as somewhat essential. Different states, however, are commonly easily reused or assembled into a whole classification description.
When reprogramming a state machine, it is important to consider a concept of a truly non-procedural method of implementing a programmable state machine. Changes to state machine programming are then added without concern for state flow, since the description of the state machine is non-procedural. Further, implementation of the state machine is performed by the compiler and does not require significant design by a state machine designer or, more importantly, an end user.
Reprogramming of a state machine having procedural programming is considered a straightforward task. State machine execution is paused, new programming is loaded into program memory and then the state machine is restarted. The process of pausing the state machine often involves halting data flow, which is undesirable. For use in firewalls and other security applications, a change in programming often results from a change in security procedures. As such, it is important to load the change as quickly as possible. Of course, it is evident to one skilled in the art that it is often impractical to shut down a system during reprogramming and, hence reprogramming of a system often only occurs at certain times. This is inconvenient.
Another problem is encountered with current reprogramming techniques for programmable state machines when several state machines share a common program memory. When upgrading the programming for any of the state machines, all state machines are paused. This is a significant problem that is possibly avoided by duplicating program memory in order to allow all but one state machine to remain operative during a reprogramming operation. Another method of avoiding this problem is to provide each state machine with dedicated state machine memory.
A current area of research in high-speed state machine design is the area of digital communications. Commonly, in digital communication networks, data is grouped into packets, cells, frames, buffers, and so forth. The packets, cells etc, contain data and classification information. It is important to classify packets, cells, etc. for routing and correctly responding to data communications. An approach to classifying data of this type uses a state machine.
For Gigabit Etheniet, it is essential that a state machine operate at very high speeds to process data in order to determine addressing and routing information as well as protocol-related information. Unfortunately, at those speeds, memory access is a significant bottleneck in implementing a state machine or any other type of real time data processor. This is driving researchers to search for innovative solutions to increase classification performance. An obvious solution is to implement a classification state machine completely in hardware. Non-programmable hardware state machines are known to have unsurpassed performance and are therefore well suited to these high data rates; however, the implementation of communication protocols is inherently flexible in nature. A common protocol today may be obsolete in a few months. Therefore, it is preferable that a state machine for use with Gigabit Ethernet is programmable. In the past, solutions for 10 Mbit and 100 Mbit Ethernet data networks required many memory access instructions per state in order to accommodate programmability. This effectively limits operating speeds of the prior art state machines.
A programmable state machine for classification of data can be implemented entirely in software. Of course, software state machines are often much slower than their hardware equivalents. In a software state machine, each operation is performed by a software instruction and state changes result in branch operations. As is evident to those of skill in the art, to implement a high-speed state machine in software for packet classification, requires many instructions per secondxe2x80x94many more than a billionxe2x80x94requiring expensive parallel processors or technologies unknown at present. In fact, a severe limitation to performance is the speed of memory devices. For example, should a 7 ns memory device be used, less than one memory access per memory device is possible for each bit of a Gigabit Ethernet stream. Thus, if each bytexe2x80x948 bitsxe2x80x94of data is processed in a single state, only one memory access operations is possible for each state. To implement such a system as a purely software solution is impractical and unlikely.
Current state of the art integrated memory devices achieve performance in the area of 7 ns per memory access when timing and other factors are taken into account. Therefore, pure hardware implementations of state machines fast enough to implement a Gigabit Ethernet packet classifier are possible so long as only one memory access is required for every 8 bits within the Ethernet data stream. Prior art implementations of such a state machine use a branching algorithm to allow state transitions within the time frame of a predetermined number of bits. The address data for the branching algorithm is stored in program memory. When the predetermined number of bits is 8, each state transition occurs within 8 ns. One method of achieving this performance is to store a table of data having 256 entries for each possible state. The table address is then concatenated with 8 bits from the data stream to determine a next state address. This continues until a value indicative of a classification or a failure to classify is encountered.
Unfortunately, the amount of memory required to implement a system, such as that described above, is prohibitive. For example, using 8 bits at a time requires up to 256 entries per table, 16 bits at a time requires 65,536 entries. The exact number of tables also depends on a number of terminal states. Since integrated memory having a high storage capacity is not available, implementation of a prior art programmable packet classification state machines having large numbers of edges in integrated memory is currently not feasible.
It has been found that a programmable hardware state machine for use in packet classification of high-speed data communications wherein reprogramming of the state machine is performed according to a non-procedural method, would be advantageous.
It would also be advantageous to provide a method of programming a state machine such that easy modification of state machine programming is possible during operation of a plurality of state machines using, the same program memory.
In order to overcome these and other limitations of the prior art, it is an object of the invention to provide state machine memory architecture for supporting a plurality of state machines simultaneously.
It is another object of the present invention to provide a method of reprogramming state machine program memory without requiring disruption of state machine operation.
In accordance with the invention there is provided a method of programming state machine memory, the state machine memory comprising a plurality of storage locations including a first state address storage location, comprising the steps of:
providing data corresponding to each new state, the data including data corresponding to all states preceding each new state including a new first state;
storing the data within the program memory, data relating to each new state stored at a state address for said new state, the data stored in unoccupied storage locations;
storing data relating to the new first state at the new first state address, the data stored in an unoccupied storage location; and
once the data corresponding to each new state is stored, replacing data within the first state address location with the new first state address.
In accordance with the invention there is provided a method of programming state machine memory wherein the state machine memory is for simultaneous use by a plurality of state machines, and wherein programming of a first state machine from the plurality of state machines is same as programming of a second state machine of the plurality of state machines. Furthermore, there is provided a method of programming state machine memory wherein programming of a first state machine from the plurality of state machines is different from programming of a second state machine of the plurality of state machines.
In different embodiments of the invention programming of the state machine is performed during execution of the state machine, and programming of the state machine is performed without interruption of execution of the state machine.
In an embodiment the state machine memory is for simultaneous use by a plurality of state machines. According to this embodiment the programming of each of the plurality of state machines may is optionally same programming or some state machines have different programming. Optionally, programming of a state machine from the plurality of state machines is performed during execution of the plurality of state machines without interruption of execution of any other state machine from the plurality of state machines; programming of a state machine from the plurality of state machines is performed during execution of the plurality of state machines without interruption of execution of any state machine from the plurality of state machines; and/or programming of a state machine from the plurality of state machines, data relating to another state machine from the plurality of state machines remains unaltered.
In accordance with the invention there is also provided a method of programming state machine memory, the state machine memory comprising a plurality of locations and a first state address storage location, comprising the steps of:
providing an image of current state machine memory on a computer;
altering the state machine programming;
determining states that are modified within the current state machine;
determining states preceding the states that are modified including a new first state;
determining unoccupied memory locations within the current state machine memory;
compiling the modified states and the states preceding the states that are modified for storage in unoccupied memory, location s within the Current state machine memory to form reprogramming data;
storing, the reprogramming data within the unoccupied memory locations within the current state machine memory;
once the reprogramming data is stored, replacing data within the first state address location with the new first state address; and,
updating the image of the current state machine.
In an embodiment the method also comprises the step of:
determining an amount of unoccupied memory;
determining if the reprogramming data will fit within the unoccupied memory; and,
when the reprogramming data will not fit within the unoccupied memory, compiling a portion of the modified states and the states that precede them to form new reprogramming data an d replacing the reprogramming data with the new reprogramming data.
In accordance with another aspect of the invention there is provided a reprogrammable state machine memory for simultaneous use by a plurality of state machines, the reprogrammable state machine memory comprising:
a program memory for storing data relating to states within each state machine, the data for each state stored at a state address;
a plurality of initial state address memory locations, each initial state address memory location for storing a first state address of a state machine from the plurality of state machines,
means for storing the data within the program memory, data relating to each new state stored at a state address for said new state and data relating to the new first state stored at the new first state address, the data stored in storage locations unoccupied by any of the plurality of state machines; and,
means for once the data corresponding to each new state is stored, replacing data within the first state address location with the new first state address.